package day21_28.day25;

import java.util.Arrays;
import java.util.Scanner;

public class Main01 {
    public static void main(String[] args) {


        Scanner scn = new Scanner(System.in);
        StringBuffer stringBuffer = new StringBuffer();
        while (scn.hasNext()){
            int n = scn.nextInt();
            int[] array = new int[n];
            for (int i = 0; i < array.length; ++i) {
                array[i] = scn.nextInt();
            }
            for (int i = 0; i < array.length; i++) {
                int x = fib(array[i]);
                String str = Integer.toString(x);
                if (str.length() == 4){
                    stringBuffer.append(str);
                }else if (str.length() < 4){
                    int y = 4 - str.length();
                    for (int j = 0; j < y; j++) {
                        stringBuffer.append(0);
                    }
                    stringBuffer.append(str);
                }else {
                    stringBuffer.append(str , str.length() - 5 , str.length());
                }

            }
            System.out.println(stringBuffer);



        }


    }
    public static int fib(int num){
        if (num == 1){
            return 1;
        }
        if (num == 2){
            return 2;
        }
        return fib(num - 1) + fib(num - 2);
    }
}
